package algorithm.middle;

import java.util.HashMap;
import java.util.PriorityQueue;

/**
 * Alice 手中有一把牌，她想要重新排列这些牌，分成若干组，使每一组的牌数都是 groupSize ，并且由 groupSize 张连续的牌组成。
 * 给你一个整数数组 hand 其中 hand[i] 是写在第 i 张牌，和一个整数 groupSize 。如果她可能重新排列这些牌，返回 true ；否则，返回 false 。
 */
public class IsNStraightHand846 {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        //维护一个 元素对应数量的map
        HashMap<Integer, Integer> map = new HashMap<>();
        //递增排序的小根堆
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int x : hand) {
            map.put(x, map.getOrDefault(x, 0) + 1);
            pq.add(x);
        }
        while (!pq.isEmpty()) {
            int t = pq.poll();
            //使用小根堆堆顺序，找到可能可以当顺子开头当数字。真实计数在map里面。
            if (map.get(t) == 0) continue;
            for (int i = 0; i < groupSize; i++) {
                int cnt = map.getOrDefault(t + i, 0);
                if (cnt == 0) return false;
                map.put(t + i, cnt - 1);
            }
        }
        return true;

    }
}
